from typing import List


class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        sum_val = sum(digits)

        if sum_val == 0:
            return "0"

        mod = sum_val % 3

        if mod == 0:
            return "".join(sorted([str(digit) for digit in digits], reverse=True))

        else:
            mod1_n1, mod1_n2 = 10, 10
            mod2_n1, mod2_n2 = 10, 10
            for digit in digits:
                if digit % 3 == 1:
                    if digit <= mod1_n1:
                        mod1_n1, mod1_n2 = digit, mod1_n1
                    elif digit < mod1_n2:
                        mod1_n2 = digit
                if digit % 3 == 2:
                    if digit <= mod2_n1:
                        mod2_n1, mod2_n2 = digit, mod2_n1
                    elif digit < mod2_n2:
                        mod2_n2 = digit

            # print("MOD MIN:", mod1_n1, mod1_n2, mod2_n1, mod2_n2)

            if mod == 1:
                if mod1_n1 != 10:
                    digits.remove(mod1_n1)
                    return "".join(sorted([str(digit) for digit in digits], reverse=True))
                else:
                    digits.remove(mod2_n1)
                    digits.remove(mod2_n2)
                    return "".join(sorted([str(digit) for digit in digits], reverse=True))
            if mod == 2:
                if mod2_n1 != 10:
                    digits.remove(mod2_n1)
                    return "".join(sorted([str(digit) for digit in digits], reverse=True))
                else:
                    digits.remove(mod1_n1)
                    digits.remove(mod1_n2)
                    return "".join(sorted([str(digit) for digit in digits], reverse=True))


if __name__ == "__main__":
    print(Solution().largestMultipleOfThree([8, 1, 9]))  # 981
    print(Solution().largestMultipleOfThree([8, 6, 7, 1, 0]))  # 8760
    print(Solution().largestMultipleOfThree([1]))  # ""
    print(Solution().largestMultipleOfThree([0, 0, 0, 0, 0, 0]))  # 0

    # 测试用例5/25
    print(Solution().largestMultipleOfThree([5, 8]))  # False
